Conjunto finito no vacio, sin elementos que se obtengan por yuxtaposicion (poner dos letras consecutivas).

Se simboliza con la letra V o con \sum

Clausura de Kleene de un Alfabeto

V=V0V1V2VnV^*= V^0\cup V^1\cup V^2\cup\cdots V^n\\ ViV^i: conjunto de palabras de longitud ii formadas con las letras del alfabeto VV\\ Entonces VV^* sera el conjunto de todas las palabras, de cualquier longitud, que se puede escribir con letras del alfabeto.

Inversion o trasposicion: es la palabra que se obtiene al escribir dicha palabra de "atras hacia adelante" se simboliza wRw^R

Sea ww una palabra V,w\in V^*,w es palindromo     w=wR\iff w=w^R

Sea wVw\in V^* se define:

{w0=λw1=wcon nN0wn=wwn1\begin{cases} w^0=\lambda\\ w^1 = w & \text{con }n\in\N_0\\ w^n = w\cdot w^{n-1} \end{cases}

Lenguaje

Sea LL un conjunto y VV un alfabeto. LL es un lenguaje     LV\iff L \sube V^*

Concatencaion de Lenguajes

L=L1L2={xy/xL1yL2}L = L_1\cdot L_2 = \{xy/x\in L_1 \land y\in L_2\}

  1. L1L2L1L2\lvert L_1\cdot L_2\rvert \leq \lvert L_1\rvert \cdot \lvert L_2\rvert
  2. (P(V);)(P(V^*);\bullet) semigrupo con neutro L=ΛL=\Lambda
  3. L1L2L2L1L_1\cdot L_2 \neq L_2\cdot L_1
  4. L=L=\varnothing es elemento absorbente de la concatenacion.
  5. Si L1L2L_1\sub L_2 y L3L4L_3\sub L_4 entonces L1L3L2L4L_1\cdot L_3 \sub L_2\cdot L_4

Lenguaje inverso reflejo o traspuesto:

LR={wR/wL}L^R=\{w^R/w\in L\}, son todas las palabras del lenguaje reflejadas.

Potencia de un Lenguaje

{L0={λ}L1=Lcon nN0Ln=LLn1\begin{cases} L^0 = \{\lambda\} \\ L^1 = L & \text{con }n\in\N_0\\ L^n= L\cdot L^{n-1} \end{cases}

Clausura de Kleene de un Lenguaje

L=n=0Ln=L0L1L2LnL^*= \bigcup_{n=0}^\infin L^n= L^0\cup L^1\cup L^2\cup \cdots \cup L^n\cup \cdots

Clausura Positiva de un Lenguaje

L+=n=1Ln=L1L2LnL^+= \bigcup_{n=1}^\infin L^n= L^1\cup L^2\cup \cdots \cup L^n\cup \cdots

Complemento de un Lenguaje

L=VL\overline{L}=V^*-L

Gramatica

G=(Vn;Vt;P;S)G=(V_n;V_t;P;S)\\ Vn:V_n: Vocabulario o alfabeto de no terminales.\\ Vt:V_t: Vocabulario o alfabeto de Terminales. Letras con las que se forman las palabras.\\ P:P: Producciones.\\ S:S: Simbolo o variable inicial.

Tipos de Gramaticas (Jerarquia de Chomsky)

Tipo Nombre Producciones
0 Irrestricta Cualquier forma
1 Sensible al Contexto aXbaYbaXb\to aYb donde a,b,YV  XVn\\ a,b,Y\in V^* \;X\in V_n
2 Independiente del Contexto XYX\to Y donde XVnX\in V_n
3 Regular XYX\to Y donde XVnYX\in V_n \\ Y puede ser Vt,tVt,t o λ\lambda (derecha) Y\\ Y puede ser tV,ttV,t o λ\lambda (izquierda)

Un lenguaje puede estar generado por distintas gramaticas de distinto tipo para un mismo lenguaje, pero el tipo del lenguaje sera el de la gramatica de mayor tipo.

Cada gramatica genera un unico lenguaje

Cada lenguaje puede ser generado por muhas gramaticas.

Expresiones Regulares

Una ER es una secuencia de elementos que verifica:+

Automatas Finitos

Maquinas de estados finitos

Lenguaje Tipo Maquina que lo Reconoce
0 Mauina de Turing
1 Automata linealmente Acotado
2 Automata de Pila (Push Down)
3 Automata Finito

Automata Finito

A=(Q,V,λ,q0,F)A=(Q,V,\lambda,q_0,F)\\ Q:Q: Conjunto finito de estados V:V: vocabulario o alfabeto de enrtada λ:\lambda: Q×VQQ\times V\to Q. Funcion de transision q0:q_0: Estado Inicial F:F: Conjunto de estados finales FF\neq \varnothing y FQF\sub Q

\, xx yy
q0q_0 q0,q1q_0,q_1 q1q_1
q1q_1 q2q_2
q2q_2 q1q_1
  1. p=aqp = a\cdot q
digraph regla1 { rankdir = LR; p -> q [label=a]; }
  1. p=aq+brp= a\cdot q + b\cdot r
digraph regla2 { rankdir = LR; p -> q [label=a]; p -> r [label=b]; }
  1. p=app=ap= a\cdot p \rArr p= a^*
digraph regla3 { rankdir = LR; p -> p [label=a]; }
  1. p=ap+bqp=a(bq)p = a\cdot p + b\cdot q \rArr p= a^*\cdot(b\cdot q)
digraph regla4 { rankdir = LR; p -> p [label=a]; p -> q [label=b]; }
  1. p=λp=\lambda
digraph regla4 { rankdir = LR; p[shape=doublecircle]; }